package net.zjitc.list.link;

import net.zjitc.list.arrays.MyList;

public class MyLinkedList<T> implements MyList<T> {
    private int size = 0;
    /**
     * 节点类
     * first=头结点
     * last=尾节点
     */
    private Node<T> first;
    private Node<T> last;

    public MyLinkedList() {
    }

    //添加
    @Override
    public boolean add(T data) {
        Node<T> node = new Node<>(data);
        linkedDefault(node);

        return true;

    }


    /**
     * 将元素插入到制定节点之前
     * A 0 B
     * 将元素插入到0的位置步骤：
     * 1.如果index=0，则说明此时时元素添加到头部
     * 2.根据下表获取到0位置前一个节点A以及后一个节点B
     * 3.然后将元素封装成一个节点newNode，newNode的next指向节点B
     * 4.将前一个节点A的next指向newNode
     *
     * @param index
     * @param data
     * @return
     */
    @Override
    public boolean add(int index, T data) {
        Node<T> node = new Node<>(data);
        //判断插入时index的范围
        if (index < 0 || index > size) {
            throw new RuntimeException("插入越界");
        }
        if (index == size) {
            linkedDefault((Node<T>) node);
        } else if (index == 0) {
            node.next = first;
            first = node;
            size++;
        } else {

            Node<T> d = first;
            for (int i = 0; i < index - 1; i++) {
                d = d.next;
            }
            node.next = d.next;
            d.next = node;
            size++;
        }
        return true;
    }

    //add index=size时
    private void linkedDefault(Node<T> node) {
        if (first == null) {
            first = node;
            last = first;
            size++;
        } else {
            last.next = node;
            last = last.next;
            size++;
        }
    }

    /**
     * 删除指定元素，如果有多个相同元素，就删除第一个
     * 注意：若链表里面有两个或两个以上的相同元素，值移除第一找到的元素
     * 步骤：
     * 1.定义两个节点：一个是需要删除元素的节点current，另一个是需要删除节点的上一个节点prevuious（都让他们从first节点开始）
     * 2.然后通过需要删除的袁旭data，找到data所对应的节点以及上一个节点
     * 3.若被删除的节点是头节点（此时current和previous都是first节点），就直接将first的下一个节点重写定义为头节点
     * 4.若删除的节点不是头节点，就将被删除的上一个节点（previous）的next指向被删除节点（current）的下一个节点
     * 5.再将sizr-1
     *
     * @param data
     * @return
     */
    @Override
    public T remove(T data) {
        if (size == 0) {
            throw new RuntimeException("链表为空");
        }
        Node<T> current = first;//将要删除的节点
        Node<T> previous = first;//将要删除的上一个节点
        while (current.data != data) {
            //current.next==null表示整个链表循环结束，没有找到需要被删除的data
            if (current.next == null) {
                System.out.println("没有找到需要删除的对象");
            } else {
                previous = current;
                current = current.next;
            }
        }
        //被删除的时头节点
        if (current == first) {
            first = first.next;
        } else {
            previous.next = current.next;
        }
        size--;
        return null;
    }


    /**
     * 删除指定位置的元素
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        Node<T> node = first;
        Node<T> oldData = null;
        if (index < 0 || index >= size) {
            throw new RuntimeException("元素下标越界");
        } else {
            if (index == 0) {
                first = node.next;
                node.next = null;
                size--;
            } else {
                for (int i = 0; i < index - 1; i++) {
                    node = node.next;
                }
                node.next = oldData;
                node.next = node.next.next;
                if (index == size - 1) {
                    last = node;
                }
                size--;
            }
        }
        return null;
    }


    /**
     * 更改指定位置元素值
     * 步骤：
     * 1.判断下表是否越界
     * 2.根据下表找到指定节点
     * 3.然后将节点的值改掉
     *
     * @param index
     * @param data
     * @return
     */
    @Override
    public boolean set(int index, T data) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("元素下标越界");
        }
        Node<T> node = first.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        node.data = data;
        return true;
    }


    /**
     * 获取指定位置元素的值
     *
     * @param index
     * @return
     */
    @Override
    public T getValue(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("元素下标越界");
        }
        Node<T> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.data;
    }


    /**
     * 获取链表长度
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }


    //toString
    @Override
    public String toString() {
        return "MyLinkedList{" +
                "size=" + size +
                ", first=" + first +
                ", last=" + last +
                '}';
    }

    public Node<T> reverseList() {
        Node<T> newFirst = null;
        Node<T> node;
        while (first != null) {
            //对之前的链表头节点删除
            node = first;
            first = first.next;

            //对新链表头节点插
            node.next = newFirst;
            newFirst = node;
        }
        return newFirst;
    }

    /**
     * 双链表合二为一有序
     */

}
